/**
 * @作者 zxy
 * @时间 2023-05-01 20:01
 * @说明 766. 托普利茨矩阵
 * 给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
 * 如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
 * 示例 1：
 * 输入：matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
 * 输出：true
 * 解释：
 * 在上述矩阵中, 其对角线为:
 * "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
 * 各条对角线上的所有元素均相同, 因此答案是 True 。
 */
public class Solution {
    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：42.3 MB, 在所有 Java 提交中击败了5.23%的用户
     * @param matrix
     * @return
     */
    public boolean isToeplitzMatrix(int[][] matrix) {
        int i = matrix.length - 1, j = 0;
        int x;
        while (j < matrix[0].length) {
            x = matrix[i][j];
            int i1 = i, j1 = j;
            while (i1 + 1 < matrix.length && j1 + 1 < matrix[0].length) {
                if (matrix[i1 + 1][j1 + 1] != x) return false;
                i1 += 1;
                j1 += 1;
            }
            if (i > 0) i--;
            else j++;
        }
        return true;
    }
}
